As the gap between hard drive access time and memory access time increases, it is increasingly desirable to locate more data in memory. This is increasingly important because the size of applications and data sets are increasing at a faster rate than the density of main memory. Furthermore, systems with multiprocessors may have many programs running simultaneously with each program having a relatively small number of pages of instructions and data in main memory. Hence, page faults may occur frequently. One way to increase the effective storage capacity of main memory is to compress its contents. However, conventional computer systems may be unable to efficiently manage the compressed data in main memory.
In typical computer operations, data is in near-constant motion in and out of memory; between memory and processors or between other sources and destinations. As processing speeds of computers have increased, the speed demands of compression/decompression engines have increased enormously.
Most conventional compression engines are capable of operating at data bus speeds but not at the bandwidth of, for example, a modern memory bus. This limitation slows down memory bus operations by adding latency to each transaction. A number of techniques have been employed to work around the speed loss associated with both compression and decompression.
One common technique uses multiple compression/decompression engines each of which is fed pieces of any given memory packet. Typically, the packet pieces are equally sized and very large, commonly on the order of one kilobyte or even larger. These large data “chunks” emerge from the compression engine at roughly the same compression ratio but with significant lag in comparison to bus speed. The piece sizes can vary from transaction to transaction, causing the compression engines to almost never be used at full efficiency and, more importantly, the size of compressed, data blocks varies with every transaction, putting huge demands on buffers and significantly reducing overall speed.
What is needed then, is a means of inline compression/decompression of data transmitted in computer buses that fully exploits the speed of available compression engines and exerts minimal impact on the speed and bandwidth of bus transactions as well as minimizing increased complexity of bus structures. A further need exists for such a means to efficiently use resources, such as the memory required for a table specifying the locations of the compressed data and on the compression/decompression engines themselves.